//TODO: LeetCode107. 二叉树的层次遍历 II
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

//! Ver1 从102题的层次遍历的结果中把尾插法改成头插法
class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> vv;
        if (root == nullptr) return vv;

        queue<TreeNode*> q;
        q.push(root);

        while (!q.empty())
        {
            vector<int> v;
            size_t leverSize = q.size();

            //在遍历第n+1层时 第n层的数据就已经被全部遍历完并且弹出队列了
            //所以在遍历第n+1层时 队列中就只有第n+1层的节点 因此在此时队列中的数据个数就是第n+1层的节点个数
            //可以借助循环来在将第n+2层节点入队列的同时完成只对第n+1层的节点完成遍历
            //这里不能写 i < q.size() 
            //因为q.size()是会动态变化的 每一次循环运行到这里都会调用一次size()函数来计算队列的大小 这样就不能达到想要的效果了
            for (size_t i = 0; i < leverSize; ++i) 
            
            {
                TreeNode* front = q.front();
                v.push_back(front->val);
                q.pop();

                if (front->left) q.push(front->left);
                if (front->right) q.push(front->right);
            }

            vv.insert(vv.begin(), v);
        }

        return vv;
    }
};

//! Ver2 尾插但是最后reverse
class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> vv;
        if (root == nullptr) return vv;

        queue<TreeNode*> q;
        q.push(root);

        while (!q.empty())
        {
            vector<int> v;
            size_t leverSize = q.size();

            //在遍历第n+1层时 第n层的数据就已经被全部遍历完并且弹出队列了
            //所以在遍历第n+1层时 队列中就只有第n+1层的节点 因此在此时队列中的数据个数就是第n+1层的节点个数
            //可以借助循环来在将第n+2层节点入队列的同时完成只对第n+1层的节点完成遍历
            //这里不能写 i < q.size() 
            //因为q.size()是会动态变化的 每一次循环运行到这里都会调用一次size()函数来计算队列的大小 这样就不能达到想要的效果了
            for (size_t i = 0; i < leverSize; ++i) 
            
            {
                TreeNode* front = q.front();
                v.push_back(front->val);
                q.pop();

                if (front->left) q.push(front->left);
                if (front->right) q.push(front->right);
            }

            vv.push_back(v);
        }
        
        reverse(vv.begin(), vv.end());
        return vv;
    }
};